package com.cqs.leetcode.array;

import com.cqs.leetcode.ds.ArraysUtils;
import com.sun.deploy.util.ArrayUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

/**
 * lixw
 * 2021/11/4
 **/
public class ShortestSubarray581 {


    class Solution {
        //排序比对
        public int findUnsortedSubarray(int[] nums) {
            int[] sorts = Arrays.copyOf(nums, nums.length);
            Arrays.sort(sorts);
            int left = 0;
            while (left < nums.length && nums[left] == sorts[left]) {
                left++;
            }
            if (left == nums.length) {
                return 0;
            }
            int right = nums.length - 1;
            while (right >= 0 && nums[right] == sorts[right]) {
                --right;
            }
            return left < right ? right - left + 1 : 0;

        }
    }


    public int findUnsortedSubarray(int[] nums) {
        if (nums.length == 1) return 0;
        //从左到右方向找到第一个打破升序的元素 eg  [1 5 9 2 4 6 7 8 10 ]  那么nums[2] idx=2 就是第一个打破升序的元素
        //nums[2] = 9 之后 找min 最小的元素. 这时候走完第一趟循环 min = 2
        //第二趟循环，找到比上一样min大的第一个元素的位置。 num[1] = 5 > 2， 第2次循环可以找到左指针
        int i = 1;
        for (; i < nums.length; i++) {
            if (nums[i - 1] > nums[i]) {
                break;
            }
        }
        //升序的
        if (i == nums.length) {
            return 0;
        }
        //剩余元素中找到比num[i]小的且是最小的元素索引
        int min = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        int left = min;
        //第二次循环 找到比第一个比nums[min]小的元素
        for (int j = 0; j <= i; j++) {
            if (nums[j] > nums[min]) {
                left = j;
                break;
            }
        }

        // 从
        int k = nums.length - 1;
        for (; k > 0; k--) {
            if (nums[k - 1] > nums[k]) {
                break;
            }
        }
        if (k <= 0) {
            //递增的
            return 0;
        }
        int max = k;
        for (int j = k - 1; j >= 0; j--) {
            if (nums[j] > nums[max]) {
                max = j;
            }
        }
        //找到一个比nums[max]小的元素
        int right = nums.length - 1;
        for (int j = nums.length - 1; j >= k; j--) {
            if (nums[max] > nums[j]) {
                right = j;
                break;
            }
        }
        return right - left + 1;
    }

    public static void main(String[] args) {
        ShortestSubarray581 s = new ShortestSubarray581();
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{2, 6, 4, 8, 10, 9, 15});
        list.add(new int[]{2, 4, 8, 10, 15});
        list.add(new int[]{15, 10, 8, 7});
        for (int[] ints : list) {
            System.out.println(ArraysUtils.formatInts(ints) + "----->" + s.findUnsortedSubarray(ints));
        }

    }
}
